The present disclosure relates generally to computational systems and methods, and relates more particularly to the encoding of information in matrices and to computational techniques involving matrix manipulations.
Interference and the ability to follow many history paths simultaneously make quantum systems attractive for implementing computations, such as may be possible with quantum computers. Efficient algorithms exploring these properties have been proposed to solve practical problems such as number factoring and unsorted database searches. These algorithms have a number of advantages compared to classically implemented algorithms, especially when quantum computers with thousands of quantum bits become available. Despite recent progress in developing quantum mechanics systems capable of processing information, the number of available quantum bits is somewhat small, e.g., in the tens of bits, making the implementation of a useful quantum computer problematic. Accordingly, a sufficiently large and resilient quantum computer that can take advantage of the above-mentioned algorithms is not yet available.
Hard computational problems are those in which the solution expressed as a number of computational steps scales faster than a power of the size of the input data, e.g. ˜O(2nq). In attempting to find better and more efficient ways to solve hard problems with conventional computers, recent advances in the study of quantum many-body systems provide some guidance. For example, the time evolution of a large class of one-dimensional interacting systems can be efficiently simulated by expressing their wave functions in a matrix product state (MPS) form and by using a time-evolving block decimation (TEBD). Even though many-body interactions tend to increase the rank of the matrices over time, it is possible to use truncation along the evolution to keep the matrices relatively small, such that the resulting wave function approximates quite accurately the exact one without an exponential computation cost. In quantum systems, local interactions do not quickly entangle a one-dimensional many-body state, justifying the matrix truncation. The evaluation of classical probability distributions in the form of an MPS has also been performed in the context of non-equilibrium phenomena of physical systems.